We propose a robust, scalable, integrated methodology for community detectionand community comparison in graphs. In our procedure, we first embed a graphinto an appropriate Euclidean space to obtain a low-dimensional representation,and then cluster the vertices into communities. We next employ nonparametricgraph inference techniques to identify structural similarity among thesecommunities. These two steps are then applied recursively on the communities,allowing us to detect more fine-grained structure. We describe a hierarchicalstochastic blockmodel---namely, a stochastic blockmodel with a naturalhierarchical structure---and establish conditions under which our algorithmyields consistent estimates of model parameters and motifs, which we define tobe stochastically similar groups of subgraphs. Finally, we demonstrate theeffectiveness of our algorithm in both simulated and real data. Specifically,we address the problem of locating similar subcommunities in a partiallyreconstructed Drosophila connectome and in the social network Friendster.
展开▼
